package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 1031. 两个非重叠子数组的最大和
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/21 20:54
 */
public class MaxSumTwoNoOverlap {


    public static void main(String[] args) {
        MaxSumTwoNoOverlap test = new MaxSumTwoNoOverlap();


        // 20
//        int[] arr = {0,6,5,2,2,5,1,9,4};
//        int a = 1;
//        int b = 2;

        // 29
//        int[] arr = {3,8,1,3,2,1,8,9,0};
//        int a = 3;
//        int b = 2;

        // 31
        int[] arr = {2, 1, 5, 6, 0, 9, 5, 0, 3, 8};
        int a = 3;
        int b = 4;

        int i = test.maxSumTwoNoOverlap(arr, a, b);
        System.out.println(i);
    }

    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int length = nums.length;
        int a = Math.min(firstLen, secondLen);
        int b = Math.max(firstLen, secondLen);
        int[][] arr = new int[length][4];
        int sum = 0;
        for (int i = 0; i < a; i++) {
            sum += nums[i];
        }
        arr[a - 1][0] = sum;
        arr[a - 1][1] = sum;
        for (int i = a; i < b; i++) {
            sum += nums[i];
            arr[i][1] = arr[i - 1][1] + nums[i] - nums[i - a];
            arr[i][0] = Math.max(arr[i - 1][0], arr[i][1]);
        }
        arr[b - 1][2] = sum;
        arr[b - 1][3] = sum;
        int max = 0;
        for (int i = b; i < length; i++) {
            arr[i][1] = arr[i - 1][1] + nums[i] - nums[i - a];
            arr[i][0] = Math.max(arr[i - 1][0], arr[i][1]);
            arr[i][3] = arr[i - 1][3] + nums[i] - nums[i - b];
            arr[i][2] = Math.max(arr[i - 1][2], arr[i][3]);
            max = Math.max(max, Math.max(arr[i][1] + arr[i - a][2], arr[i][3] + arr[i - b][0]));
        }
        return max;
    }

}
